数据结构 - 二分查找

发表于 | 分类于 | | 阅读次数:
字数统计: 327 | 阅读时长 ≈ 1

针对有序数据集合的查找算法

1000 万个整数数据，每个数据占 8 个字节，如何设计数据结构和算法，快速判断某个整数是否出现在这 1000 万数据中？

该功能不要占用太多的内存空间，最多不要超过 100MB。

二分思想

O(logn) 惊人的查找速度

二分查找的递归与非递归实现

最简单的情况就是有序数组中不存在重复元素。

  1. 循环条件：low<=high

  2. mid取值：

    low 和 high 比较大的话，mid=(low+high)/2和可能会溢出。

    改进方式1为，mid=low+(high-low)/2

    改进方式2为，除以 2 操作转化成位运算 mid = low+((high-low)>>1)

  3. low和high更新

    low=mid+1，high=mid-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 循环二分查找
def search(arr, n, value):
    low = 0
    high = n - 1
    while low <= high:
        mid = int((high + low) / 2)
        if arr[mid] == value:
            return mid
        elif arr[mid] < value:
            low = mid + 1
        else:
            high = mid - 1
    return -1


# 递归二分查找
def Binarysearch(arr, low, high, value):
    if low > high:
        return -1
    # 位操作，防止溢出
    mid = low + ((high - low) >> 1)
    if arr[mid] == value:
        return mid
    elif arr[mid] < value:
        return Binarysearch(arr, mid + 1, high, value)
    else:
        return Binarysearch(arr, low, mid - 1, value)


a = [1, 2, 3, 4, 6, 8, 9]
n = len(a)
value = 1

print(search(a, n, value))
print(Binarysearch(a, 0, n - 1, value))